Stardust là album đầu tiên mà Lena không cộng tác cùng Stefan Raab, cố vấn cũ của cô. Quá trình thực hiện được bắt đầu từ cuối hè 2011 qua các chuyến đi đến Stockholm, Luân Đôn và Hamburg.[3] Để thực hiện album, cô đã cộng tác cùng nhiều nhạc sĩ như Matthew Benbrook,[4] Pauline Taylor,[4] Johnny McDaid,[5] James Flannigan,[5] và đặc biệt là Sonny Boy Gustafsson,[1] người đã sản xuất tới 5 ca khúc trong album.[6] Bốn ca khúc có sự cộng tác của Miss Li, trong đó ca khúc "ASAP" cô song ca với nữ ca sĩ-nhạc sĩ người Thuỵ Điển này.[7] Lena đồng thời cũng là đồng sáng tác của chín bản nhạc. "Better News" và "I'm Black" do cô hợp tác viết với Ian Dench, người từng là việc với EMF và Florence and the Machine. Ý tưởng của bản "Don't Panic" được lấy từ một vụ báo cháy ở Luân Đôn. "Mr Arrow Key", ca khúc sau này trở thành đĩa đơn thứ bảy của cô, viết về lý tưởng sống trong khi "Pink Elephant" kể lại câu chuyện về một cô gái vụng về như chú voi con. "Goosebumps" viết về nỗi nhớ nhà, "To the Moon" là một bản tình ca đã khiến Lena, đồng sáng tác Alexander Schroer và nhà sản xuất Swen Meyer mất bảy tháng đề viết ca từ cho phù hợp với giai điệu. "Neon (Lonely People)" miêu tả cái cảm giác cô đơn dù vẫn có bao người xung quanh.

Ngoài ra, còn có một track ẩn khác là "Lille katt" được trình bày bằng tiếng Thuỵ Điển, từng được thể hiện trong Emil i Lönneberga, một chương trình truyền hình thiếu nhi đa ngôn ngữ bằng cả tiếng Đức và tiếng Thuỵ Điển. Phiên bản phát hành trên iTunes bao gồm cả bản cover lại ca khúc Moonlight của Mayaeni được phát hành vào năm 2010.

Quá trình sản xuất album kết thúc vào tháng 7 năm 2012. Lena trình bày 8 trên 12 ca khúc trong các sự kiện giới thiệu tới báo giới và các đài phát hành tại Munich, Cologne, Hamburg và Berlin từ cuối tháng 7 tới đầu tháng 8 năm 2012. Stardust được sản xuất phần nhiều bởi Swen Meyer, tại Hamburg, người từng cộng tác với Tomte, Tim Bendzko và Kettcar.[1] Đĩa đơn cùng tên được phát hành vào ngày 21 tháng 9 năm 2012, còn MV ra lò trước đó vào ngày 7 cùng tháng. Ngày 20 tháng 9, cô giới thiệu album tới công chúng tại Reeperbahn Festival, tổ chức tại Schmidt's Tivoli, Hamburg.[7]